package org.apache.minibase;

/**rowkey可以采用字典树存储
 * @author sulei_zhang
 *
 */
public class DicTreeDemo {
	
	static class TrieNode {  
	    public TrieNode[] children;  
	    public boolean isEndOfWord;  
	    
	    // 初始化你的数据结构  
	    public TrieNode() {  
	        this.children = new TrieNode[26];  
	        this.isEndOfWord = false;  
	    }  
	}  
	  
	static class Trie {  
	    private TrieNode root;  
	    
	    // 初始化你的数据结构  
	    public Trie() {  
	        root = new TrieNode();  
	    }  
	  
	    // 插入一个单词到字典树中  
	    public void insert(String word) {  
	        TrieNode node = root;  
	        for (int i = 0; i < word.length(); i++) {  
	            char ch = word.charAt(i);  
	            int index = ch - 'a';  
	            if (node.children[index] == null) {  
	                node.children[index] = new TrieNode();  
	            }  
	            node = node.children[index];  
	        }  
	        node.isEndOfWord = true;  
	    }  
	  
	    // 搜索一个单词是否在字典树中  
	    public boolean search(String word) {  
	        TrieNode node = root;  
	        for (int i = 0; i < word.length(); i++) {  
	            char ch = word.charAt(i);  
	            int index = ch - 'a';  
	            if (node.children[index] == null) {  
	                return false;  
	            }  
	            node = node.children[index];  
	        }  
	        return node.isEndOfWord;  
	    }  
	}
	
	public static void main(String[] args) {  
	    Trie trie = new Trie();  
	    trie.insert("apple");  
	    System.out.println(trie.search("apple"));  // 返回 true  
	    System.out.println(trie.search("app"));     // 返回 false  
	}

}
